package zcw.com.lib_leet_code;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/19.<br><br>
 *
 * 下一个更大元素 I
 */
public class Topic496 {

    public static void main(String[] args) {
        Topic496 instance = new Topic496();

        int[] array1 = new int[] {4,1,2};
        int[] array2 = new int[] {1,3,4,2};
        Util.printArray(instance.nextGreaterElement(array1, array2));

        array1 = new int[] {2,4};
        array2 = new int[] {1,2,3,4};
        Util.printArray(instance.nextGreaterElement(array1, array2));
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] indexArray = new int[10001];
        for(int i = 0; i < nums2.length; i++) {
            indexArray[nums2[i]] = i;
        }

        int[] result = new int[nums1.length];
        for(int i = 0; i < result.length; i++) {
            result[i] = -1;

            for(int j = indexArray[nums1[i]] + 1; j < nums2.length; j++) {
                if(nums2[j] > nums1[i]) {
                    result[i] = nums2[j];
                    break;
                }
            }
        }

        return result;
    }

    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>();

        Deque<Integer> stack = new ArrayDeque<>();
        for(int value : nums2) {
            while (!stack.isEmpty() && stack.peek() < value) {
                map.put(stack.pop(), value);
            }

            stack.push(value);
        }

        for(int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }

        return result;
    }
}
